Digital content transmission between a server and multiple receivers over a communications channel has been the subject of much literature. In general, a design goal of a content delivery system is to allow each recipient to receive an exact copy of content transmitted over a channel by a server with some level of certainty. Hereafter, content may be a file, a stream of data or some other form of data. A content delivery system may have to serve as many different contents as there are active receivers, as each receiver may demand a different content. In addition, where different receivers request the same content at different points in time, a concern is how to efficiently serve the content to each receiver. Potentially each client may require an independent stream of the content it requested, where a stream is the flow of data from the server required by that client in order to download the content.
In this context, a content delivery protocol is defined to be an end-to-end protocol that is enacted between a sender and a receiver that is used to deliver contents to the receiver from the sender. An example of such a protocol is Transmission Control Protocol/Internet Protocol (TCP/IP). There are two fundamental services that any content delivery protocol should provide: reliability and flow/congestion control. For download applications, reliability comprises making sure that each receiving client eventually receives a bit-by-bit precise copy of the content. Flow/congestion control for time insensitive download applications comprises making sure that the rate at which data is sent to a receiver is as fast as possible but not at such a fast rate that the intermediate routers and buffers (including the receiving buffer of the client machine) are overwhelmed with too much data too fast and overflow.
For streaming applications, reliability comprises making sure that each receiving client can play out as high of quality rendition of the original stream of data or file as possible. Flow/congestion control for streaming should try to ensure that the reception rate of a receiving client is fast enough to allow the client to play out the stream at high quality with minimal or no interruptions.
Flow/congestion control must also take into account that the intervening network between the sender and the receivers is a shared network, and thus the flow/congestion control must react dynamically to changing conditions in the network due to other flows.
The most widely used Internet content delivery protocol today is TCP/IP. TCP/IP is a protocol that provides the services for reliability and flow/congestion control. A TCP sender partitions content to be delivered into input symbols that can fit into the payload of a TCP/IP packet, and each input symbol is included in a TCP/IP packet that additionally includes an indication of which input symbol the packet contains (e.g., a sequence number). The packets are then routed to their destination. Upon receipt of each such packet, a TCP receiver sends an acknowledgment back to the TCP sender indicating which input symbols the TCP receiver has fully received. Based on this feedback, the TCP sender can determine if the TCP receiver is missing any input symbols that have been sent. Over time, when there are no missing input symbols, the TCP sender continually increases the rate at which it sends packets. When sent packet(s) are not acknowledged by the TCP receiver, the TCP sender slows down the sending rate of packets significantly and also resends the packet(s) containing the missing input symbols. Thus, the acknowledgments sent from the TCP receiver to the TCP sender are used both to adjust the sending rate of packets (flow/congestion control) and to decide which input symbols to resend because they were not yet received (reliability).
Furthermore, TCP/IP performs the functions of making a connection, maintaining the connection, and terminating the connection between a TCP sender and TCP receiver.
Traditional web servers and some traditional streaming servers are based on the standardized TCP/IP protocol. FIG. 1 illustrates a traditional TCP/IP-based server 100. The server 100 includes a disk 120 that stores content to be delivered and a plurality of TCP senders 110, each coupled to a network 130. Each TCP sender 110 is associated with a connected client (not shown), and each TCP sender 110 sends packets via the network 130 to a TCP receiver on the corresponding client machine. Additionally, each TCP sender 110 must keep track of and maintain a fairly large amount of TCP state information. The TCP senders 110 each send their corresponding client a potentially different set of input symbols at the same point in time even if all clients are downloading or streaming the same content. The constraints on a web or streaming server 100 include the amount of memory used by each TCP sender 110. For example the memory dedicated to each sender 110 could be by default 64 KB, but the memory needed for each sender 110 can be much larger when the sending rate is high. For example, a sender 110 sending packets at 10 Mbps on a connection that has a 1 second round trip time to the TCP receiver will need over 1 MB of memory dedicated to the TCP sender 110 in order to store the required one round trip time of packets in flight. Another constraint of interest is the contending disk access for the different TCP senders. For example, if one hundred clients are downloading or streaming the same large content that is, for example, 1 GB in length from the server 100, and the clients started the download or stream at staggered times, then the one hundred TCP senders 110 would need to concurrently read from different portions of the disk 120. If the number of clients is instead 1,000 then the disk contention problem is ten times worse. Furthermore, the CPU resources of the server must be shared among all TCP senders 110. Thus, all TCP senders 110 on a traditional web or streaming server 100 are all competing for the same limited server resources, and thus the capacity of a server 100 to serve concurrently connected clients is linearly related to the amount of resources available on the server. Furthermore, if any of these resources is a bottleneck, then this resource will dictate the capacity of the server in terms of concurrent client downloads or streams.
Beyond all the issues listed above that affect both TCP/IP-based web and streaming servers, traditional TCP/IP-based streaming servers have the additional concern that each client should be served at a rate that is at least the playback rate of the stream in order to avoid unwanted stoppages in the playback of the stream at the client. Thus, consistent sending above a minimal rate is a more important requirement for a streaming server than it is for a web server for download applications. Primarily for this scalability reason, streaming servers use User Datagram Protocol (UDP) whenever possible with either unicast or multicast connections to the clients.
Using UDP introduces a number of other concerns, including that of flow/congestion control and reliability. A simple use of UDP is to transmit the raw stream in packets to all clients at a fixed rate. One issue with this approach is that such a transmission is not reactive to congestion in the network, and may cause the intervening networking infrastructure to overload. Such an overload may cause massive packet loss and may negatively impact other connections sharing the same network infrastructure. Another concern is that such a transmission is not protected against losses, and thus even when a substantial fraction of packets do arrive at clients, the play out quality may be quite poor when there are packet losses containing important piece of the original stream. For example, with Moving Picture Experts Group (MPEG) streams, the loss of packets containing I-frames may cause many frames of the play out to display incorrectly.
In several other works, an approach has been introduced for ensuring reliable content delivery using FEC codes such as Reed-Solomon codes or Tornado codes, or chain reaction codes which are information additive codes. The basic idea is to send output symbols generated from the content instead of just the input symbols that constitute the content. Erasure correcting codes, such as Reed-Solomon or Tornado codes generate a fixed number of output symbols for a fixed length content. For example, for K input symbols, N output symbols might be generated. These N output symbols may comprise the K original input symbols and N-K redundant symbols. If storage permits, then the server can compute the set of output symbols for each content only once and transmit the output symbols using a carousel protocol.
More recently, chain reaction coding systems have been developed for use in content transmission systems. U.S. Pat. No. 6,307,487, U.S. Pat. No. 6,320,520, U.S. Pat. No. 6,486,803 and U.S. Pat. No. 6,411,223 describe various chain reaction coding systems in detail. As described therein, a chain reaction encoder generates output symbols from input symbols of the content as needed. The server can continuously generate output symbols for each content being served.
For traditional FEC codes, the number of possible output symbols that can be generated is of the same order of magnitude as the number of input symbols the content is partitioned into. Typically, most or all of these output symbols are generated in a preprocessing step before the sending step. These output symbols have the property that all the input symbols can be regenerated from any subset of the output symbols equal in length to the original content or slightly longer in length than the original content. For chain reaction codes, the pool of possible output symbols that can be generated is orders of magnitude larger than the number of the input symbols, and a random output symbol from the pool of possibilities can be generated very quickly. For chain reaction codes, the output symbols can be generated on the fly on an as needed basis concurrent with the sending step. Chain reaction codes have the property that all input symbols of the content can be regenerated from any subset of a set of randomly generated output symbols slightly longer in length than the original content.
Therefore, what is needed is a server that does not require excessive computing power or memory at a sender to implement, and that can be used to efficiently distribute a plurality of contents that are continuously being encoded.